package practice1_100;

import java.util.Arrays;

public class Practice416 {
    int sum=0;
    public boolean canPartition(int[] nums){
        for (int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        sum=sum/2;
        //Arrays.sort(nums);
        boolean[][] count=new boolean[nums.length+1][sum+1];
        for (int i=0;i<=nums.length;i++){
            count[i][0] =true;
        }
//        Arrays.fill(count,false);
        for (int i=1;i<=nums.length;i++){
            for (int j=1;j<=sum;j++){
                if(j-nums[i-1]<0)
                    count[i][j]=count[i-1][j];
                else
                    count[i][j] = count[i - 1][j] || count[i - 1][j-nums[i-1]];
            }
        }
    return count[nums.length][sum];


    }


    public static void main(String[] args) {
//
        boolean a= new Practice416().canPartition(new int[]{2,5,3,5,6,4,7,3,4,7,2,4,8,4,6,4,6,4,6,4,8,6,4,8,2,1,6,7});
        System.out.println(a);
    }




    //再做一遍
    public boolean canPartition1(int[] nums){
        int sum=0;
        for (int num:nums){
            sum+=num;
        }
        if(sum%2==1) return false;//总和不能被2整除，一定不能

        //可以用回溯法开解体

    return  false;
    }

    public boolean dp(int[] nums,int index,int amount,int current){
        if( index>=nums.length) return false;
        if(current==amount) return true;
        if(nums[index]+current<amount){

        }
        //取当前index
        boolean a=   dp(nums,index+1,amount,nums[index]+current);
        //不取当前index
        boolean b=dp(nums,index+1,amount,current);

        return a||b;
//        for (int i=0;i<nums.length;i++){
//            current
//        }
    }
}
